#include <stdio.h>
#include <string.h>

void getNext(const char *pattern, int *next) {
    int len = strlen(pattern);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void getNextVal(const char *pattern, int *nextval, int *next) {
    int len = strlen(pattern);
    for (int i = 0; i < len; i++) {
        if (pattern[i] == pattern[next[i]]) {
            nextval[i] = nextval[next[i]];
        } else {
            nextval[i] = next[i];
        }
    }
}

int main() {
    char pattern[] = "abcaabbabcab";
    int next[13];
    int nextval[13];
    getNext(pattern, next);
    getNextVal(pattern, nextval, next);
    printf("Next values: ");
    for (int i = 0; i < 13; i++) {
        printf("%d ", next[i]);
    }
    printf("\nNextVal values: ");
    for (int i = 0; i < 13; i++) {
        printf("%d ", nextval[i]);
    }
    return 0;
}

/*
1. 求模式串\(t='abcaabbabcab'\)的 next 函数值：
   - 首先，next 函数的定义是：对于模式串\(t\)，next\[j\]表示当模式串的第\(j\)个字符与主串相应字符不匹配时，模式串应该跳到的位置。
   - 初始化\(next[0]=-1\)，\(next[1]=0\)。
   - 对于\(j = 2\)，比较\(t[1]\)与\(t[0]\)，因为\(t[1] = 'b'\neq t[0] = 'a'\)，所以\(next[2]=0\)。
   - 对于\(j = 3\)，比较\(t[2]\)与\(t[0]\)，因为\(t[2] = 'c'\neq t[0] = 'a'\)，所以\(next[3]=0\)。
   - 对于\(j = 4\)，比较\(t[3]\)与\(t[0]\)，因为\(t[3] = 'a'\)等于\(t[0] = 'a'\)，所以\(next[4]=1\)。
   - 对于\(j = 5\)，比较\(t[4]\)与\(t[next[4]]\)，即比较\(t[4] = 'a'\)与\(t[1] = 'b'\)，不相等，所以\(next[5]=0\)。
   - 对于\(j = 6\)，比较\(t[5]\)与\(t[0]\)，因为\(t[5] = 'b'\neq t[0] = 'a'\)，所以\(next[6]=0\)。
   - 对于\(j = 7\)，比较\(t[6]\)与\(t[0]\)，因为\(t[6] = 'b'\neq t[0] = 'a'\)，所以\(next[7]=0\)。
   - 对于\(j = 8\)，比较\(t[7]\)与\(t[0]\)，因为\(t[7] = 'a'\)等于\(t[0] = 'a'\)，所以\(next[8]=1\)。
   - 对于\(j = 9\)，比较\(t[8]\)与\(t[next[8]]\)，即比较\(t[8] = 'b'\)与\(t[1] = 'b'\)，相等，所以\(next[9]=2\)。
   - 对于\(j = 10\)，比较\(t[9]\)与\(t[next[9]]\)，即比较\(t[9] = 'c'\)与\(t[2] = 'c'\)，相等，所以\(next[10]=3\)。
   - 对于\(j = 11\)，比较\(t[10]\)与\(t[next[10]]\)，即比较\(t[10] = 'a'\)与\(t[3] = 'a'\)，相等，所以\(next[11]=4\)。
   - 对于\(j = 12\)，比较\(t[11]\)与\(t[next[11]]\)，即比较\(t[11] = 'b'\)与\(t[4] = 'a'\)，不相等，继续比较\(t[11]\)与\(t[next[4]]\)，即比较\(t[11] = 'b'\)与\(t[1] = 'b'\)，相等，所以\(next[12]=2\)。

   综上，模式串\(t='abcaabbabcab'\)的 next 函数值为\([-1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 3, 4, 2]\)。

2. 求模式串\(t='abcaabbabcab'\)的 nextval 函数值：
   - nextval 函数的定义是：当模式串的第\(j\)个字符与主串相应字符不匹配时，模式串应该跳到的位置的字符与第\(j\)个字符比较的结果。
   - 初始化\(nextval[0]=-1\)。
   - 对于\(j = 1\)，因为\(next[1]=0\)，且\(t[1] = 'b'\neq t[0] = 'a'\)，所以\(nextval[1]=next[1]=0\)。
   - 对于\(j = 2\)，因为\(next[2]=0\)，且\(t[2] = 'c'\neq t[0] = 'a'\)，所以\(nextval[2]=next[2]=0\)。
   - 对于\(j = 3\)，因为\(next[3]=0\)，且\(t[3] = 'a'\neq t[0] = 'a'\)，所以\(nextval[3]=next[3]=0\)。
   - 对于\(j = 4\)，因为\(next[4]=1\)，且\(t[4] = 'a'\neq t[next[4]] = t[1] = 'b'\)，所以\(nextval[4]=next[4]=1\)。
   - 对于\(j = 5\)，因为\(next[5]=0\)，且\(t[5] = 'b'\neq t[0] = 'a'\)，所以\(nextval[5]=next[5]=0\)。
   - 对于\(j = 6\)，因为\(next[6]=0\)，且\(t[6] = 'b'\neq t[0] = 'a'\)，所以\(nextval[6]=next[6]=0\)。
   - 对于\(j = 7\)，因为\(next[7]=0\)，且\(t[7] = 'a'\neq t[0] = 'a'\)，所以\(nextval[7]=next[7]=0\)。
   - 对于\(j = 8\)，因为\(next[8]=1\)，且\(t[8] = 'b'\neq t[next[8]] = t[1] = 'b'\)，所以\(nextval[8]=next[8]=1\)。
   - 对于\(j = 9\)，因为\(next[9]=2\)，且\(t[9] = 'c'\neq t[next[9]] = t[2] = 'c'\)，此时需要继续比较\(t[9]\)与\(t[next[2]]\)，即\(t[9] = 'c'\neq t[0] = 'a'\)，所以\(nextval[9]=next[9]=2\)。
   - 对于\(j = 10\)，因为\(next[10]=3\)，且\(t[10] = 'a'\neq t[next[10]] = t[3] = 'a'\)，此时需要继续比较\(t[10]\)与\(t[next[3]]\)，即\(t[10] = 'a'\neq t[0] = 'a'\)，所以\(nextval[10]=next[10]=3\)。
   - 对于\(j = 11\)，因为\(next[11]=4\)，且\(t[11] = 'b'\neq t[next[11]] = t[4] = 'a'\)，此时需要继续比较\(t[11]\)与\(t[next[4]]\)，即\(t[11] = 'b'\neq t[1] = 'b'\)，所以\(nextval[11]=next[11]=4\)。
   - 对于\(j = 12\)，因为\(next[12]=2\)，且\(t[12] = 'b'\neq t[next[12]] = t[2] = 'c'\)，此时需要继续比较\(t[12]\)与\(t[next[2]]\)，即\(t[12] = 'b'\neq t[0] = 'a'\)，所以\(nextval[12]=next[12]=2\)。

   综上，模式串\(t='abcaabbabcab'\)的 nextval 函数值为\([-1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 3, 4, 2]\)。需要注意的是，这里 nextval 函数值与 next 函数值相同是由于模式串的特殊性导致的。一般情况下，nextval 函数值与 next 函数值不一定相同。
*/